package com.Algorithm.greedy;

import java.util.*;

/**
 * 贪心算法
 * 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
 *
 * 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
 * @author MaoLin Wang
 * @date 2019/11/1612:43
 */
public class GreedyDemo {
    /**
     * 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）
     * 将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
     * 重复第1步直到覆盖了全部的地区
     * @param args
     */
    public static void main(String[] args) {
        //创建电台
        Map<String, HashSet<String>> map=new HashMap<>();

        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");
        map.put("K1",hashSet1);

        HashSet<String> hashSet2 = new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        map.put("K2",hashSet2);

        HashSet<String> hashSet3 = new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        map.put("K3",hashSet3);

        HashSet<String> hashSet4 = new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");
        map.put("K4",hashSet4);

        HashSet<String> hashSet5 = new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");
        map.put("K5",hashSet5);


        HashSet<String>allAreas=new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("杭州");
        allAreas.add("大连");
        allAreas.add("成都");
        allAreas.add("深圳");
        allAreas.add("广州");

        //存放已选择的电台
        List<String> selected=new ArrayList<>();

        HashSet<String>tempSet=new HashSet<>();


        //保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
        String maxKey=null;

        while (allAreas.size()!=0){//尚未覆盖完毕
            maxKey=null;

            for (String key:map.keySet()){
                tempSet.clear();
                //当前电台可覆盖的地区
                HashSet<String> areas = map.get(key);
                tempSet.addAll(areas);

                tempSet.retainAll(allAreas);
                if (tempSet.size()>0 &&
                        (maxKey==null || tempSet.size()>map.get(maxKey).size()) ){
                    maxKey=key;
                }
            }
            if (maxKey!=null){
                selected.add(maxKey);
                //清除maxkey指向的地区清除掉
                allAreas.removeAll(map.get(maxKey));
            }

        }

        System.out.println("结果:");
        System.out.println(selected);

    }
}
